#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> arr;
void show(vector<int> &arr)
{
    for (auto &it : arr)
        printf(" %d", it);
    printf("\n");
};
void qqSort(vector<int> &arr, int l, int r)
{
    if (l >= r)
        return;
    swap(arr[(l + r) / 2], arr[r]);
    int i = l - 1, pivot = arr[r];
    for (int j = l; j < r; ++j)
        if (arr[j] < pivot)
            swap(arr[++i], arr[j]);
    swap(arr[i + 1], arr[r]);
    show(arr);
    qqSort(arr, l, i);
    qqSort(arr, i + 2, r);
}
void qSort(vector<int> &arr, int l, int r)
{
    if (l >= r)
        return;
    int i = l - 1, j = r + 1, pivot = arr[(l + r + 1) / 2];
    while (i < j)
    {
        do
        {
            i++;
        } while (arr[i] <= pivot);
        do
        {
            j--;
        } while (pivot <= arr[j]);
        if (i < j)
            swap(arr[i], arr[j]);
    }
    show(arr);
    if (l < j)
        qSort(arr, l, j);
    if (i < r)
        qSort(arr, i, r);
}
int main()
{
    // arr = {18, 2, 3, 5};
    // show(arr);
    // qqSort(arr, 0, arr.size() - 1);
    // show(arr);
    arr = {18, 2, 3, 5};
    show(arr);
    qSort(arr, 0, arr.size() - 1);
    show(arr);
    return 0;
}